1. Field of the Invention
This invention relates to the frequency separation of image data.
2. Description of the Prior Art
Frequency-separation of image data is a well-established technique, and is particularly useful as part of a data compression process. The image data can be divided into different spatial frequency bands, and a different degree of quantisation or other lossy processing applied to the bands in dependence on the relative importance of each band to the reconstructed picture.
One recently proposed technique for image data frequency separation is the so-called "wavelet" coding technique. In this technique, the resulting spatial frequency bands vary in size in dependence on the frequency range of the bands.
An example of the wavelet coding technique is illustrated schematically in FIGS. 1a to 1d of the accompanying drawings. An input image 10 (FIG. 1a) is horizontally and vertically decimated (by a decimation factor of two in each direction) to form four spatial frequency bands 1, 2, 3 and 4 (FIG. 1b).
In FIGS. 1b, 1c and 1d, horizontal spatial frequency increases from band to band in a left-to-right horizontal direction, and vertical spatial frequency increases from band to band in a top-to-bottom vertical direction. Accordingly, in FIG. 1b, the top left band 1 represents the lowest horizontal and vertical spatial frequencies.
As shown in FIG. 1c, the band 1 (but not the bands 2, 3 and 4) is then horizontally and vertically decimated to form four further bands, 1.1, 1.2, 1.3 and 1.4. Of these, only the lowest spatial frequency band 1.1 is further separated to form bands 1.1.1, 1.1.2, 1.1.3 and 1.1.4.
FIG. 2 of the accompanying drawings schematically illustrates a previously proposed wavelet encoder, and FIGS. 3a to 3c of the accompanying drawings schematically illustrate the data structure within line buffers of the encoder of FIG. 2.
In FIG. 2, input image data is subjected to horizontal and vertical decimation by a first horizontal and vertical filter stage 20. (Suitable filters are described in British published patent application no. 2 262 854). The four spatial frequency bands generated by the first filtering stage 20 (i.e. the bands 1, 2, 3 and 4 of FIG. 1b) are then passed, multiplexed together, to a second filter stage 30. This stage decimates the band 1 to generate the four bands 1.1, 1.2, 1.3 and 1.4 and passes these, together with the bands 2, 3 and 4 (which have not been filtered by the second stage 30) to a third filter stage 40. The third filter stage 40 decimates the band 1.1 to generate the bands 1.1.1, 1.1.2, 1.1.3 and 1.1.4. The entire band structure of FIG. 1d is then output by the third filter stage 40.
Each filter stage 20, 30 and 40 comprises horizontal and vertical multi-tap finite impulse response (FIR) decimation filters. The horizontal FIR filters simply process groups of samples along a single line of the image, but the vertical FIR filters require line buffers or memories 50, 60 and 70 to provide line-delayed samples for the filtering process.
The line buffer 50, associated with the first filter stage 20, has to store n lines for an n-tap vertical filtering process. However, because of the way in which the output data from the first and second filter stages is multiplexed together (to be described below with reference to FIGS. 3a to 3c of the accompanying drawings) the line buffers 60 and 70 have to store 2n lines and 4n lines respectively.
FIGS. 3a to 3c schematically illustrate the data structures in the line buffers 50, 60 and 70 respectively.
FIG. 3a shows the structure of the line buffer 50, which is one line wide (in this example, 720 samples wide) and n lines deep to allow for an n-tap vertical filtering process carried out by the first filter stage 20.
In the data output by the first filter stage 20, samples from the four bands 1, 2, 3 and 4 are multiplexed together in square groups of four (2.times.2) samples. The second filter stage filters only those samples from the band 1 (shown shaded in FIG. 3b), but because such samples occur only every second line of the multiplexed data generated by the first filter stage 20, in order to buffer a vertical group of n samples from band 1 a 2n-line buffer 60 is required.
The second filter stage 30 generates output data in which the four bands 1.1, 1.2, 1.3 and 1.4 are multiplexed with data representing bands 2, 3 and 4 from the first filter stage 20. The third filter stage acts only on samples from the band 1.1, but since these occur only every fourth line of data from the second filter stage, the line buffer 70 has to store 4n lines to perform an n-tap vertical filtering operation.
Wavelet encoders of the type illustrated in FIG. 1 are often implemented as application specific integrated circuits (ASICs). However, it is a severe burden to have to provide the line buffers 50, 60, 70 to store n+2n+4n lines of image data. Indeed, in order to produce line buffers of this type it is often necessary to use up to 5 ASIC gates per stored bit.